public class MajorityElement {
    public static void main(String[] args) {
        int nums[] = {3,2,3};
        int res = getMajorityElement(nums,0,nums.length-1);
        System.out.println(res);
    }
    public static int getMajorityElement(int nums[],int left,int right){
           if (left == right) {
                return nums[left];
            }
            int mid = left + (right - left) / 2;
            int leftMajority = getMajorityElement(nums, left, mid);
            int rightMajority = getMajorityElement(nums, mid + 1, right);
            if (leftMajority == rightMajority) {
                return leftMajority;
            }
            int leftCount = 0;
            int rightCount = 0;
            int size = nums.length;
            for (int i = 0 ; i <size ;i++){
                if (nums[i] == leftMajority){
                    leftCount++;
                }else if (nums[i] == rightMajority){
                    rightCount++;
                }
            }
            return leftCount > rightCount ? leftMajority : rightMajority;
    }
}
